#ifndef _KZMAP_H_
#define _KZMAP_H_

template<typename K, typename V>
class node {
public:
    K key;
    V value;
    node<K, V>* next;

    node(const K& k, const V& v) : key(k), value(v), next(nullptr) {}
};

template<typename K, typename V>
class nodelist {
public:
    nodelist() : head(nullptr), size(0) {}
    ~nodelist() {
        clear();
    }

    // add to tail
    void append(const K& key, const V& value)
    {
        if (find(key) != nullptr) {
            return;
        }

        node<K, V>* newNode = new node<K, V>(key, value);
        if (newNode == nullptr) {
            return;
        }

        if (head == nullptr) {
            head = newNode;
        } else {
            node<K, V>* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
        size++;
    }

    // add from head
    void prepend(const K& key, const V& value)
    {
        if (find(key) != nullptr) {
            return;
        }

        node<K, V>* newNode = new node<K, V>(key, value);
        if (newNode == nullptr) {
            return;
        }

        newNode->next = head;
        head = newNode;
        size++;
    }

    // delete by key
    bool remove(const K& key)
    {
        if (head == nullptr) {
            return false;
        }
        
        if (head->key == key) {
            node<K, V>* toDelete = head;
            head = head->next;
            delete toDelete;
            size--;
            return true;
        }
        
        node<K, V>* current = head;
        while (current->next != nullptr && current->next->key != key) {
            current = current->next;
        }
        
        if (current->next == nullptr) {
            return false;
        }
        
        node<K, V>* toDelete = current->next;
        current->next = toDelete->next;
        delete toDelete;
        size--;
        return true;
    }

    node<K, V>* find(const K& key) const
    {
        node<K, V>* current = head;
        while (current != nullptr) {
            if (current->key == key) {
                return current;
            }
            current = current->next;
        }
        return nullptr;
    }

    bool exist(const K& key) const
    {
        return find(key) != nullptr;
    }

    node<K, V>* findByKey(const K& key) const
    {
        node<K, V>* current = head;
        while (current != nullptr) {
            if (current->key == key) {
                return current;
            }
            current = current->next;
        }
        return nullptr;
    }

    node<K, V>* operator[](int index)
    {
        if (index < 0 || index >= size) {
            return nullptr;
        }

        node<K, V>* current = head;
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        return current;
    }

    V& key(const K& key)
    {
        node<K, V>* node = findByKey(key);
        if (node == nullptr) {
            append(key, V());
            node = findByKey(key);
        }
        return node->value;
    }

    int nodeMax() const { return size; }
    bool isEmpty() const { return size == 0; }

    void clear() {
        while (head != nullptr) {
            node<K, V>* toDelete = head;
            head = head->next;
            delete toDelete;
        }
        size = 0;
    }

private:
    node<K, V>* head;
    int size;
};

#endif